package sortAlgorithm;

// 快速排序
public class QuickSort {
    public static void quickSort(int[] array, int left,int right){
        if (left > right)
        {
            return;
        }

        int i = left,j = right;
        int base = array[left]; // 用数组最左边的数为基准数
        while(i != j){

            // 这里两个顺序需要注意
            // 从右侧找到一个比base小的值
            while(array[j] > base && i < j){
                j--;
            }

            // 从左侧找到一个比base大的值
            while(array[i] <= base && i < j){
                i++;
            }

            //交换找到的值,使左边小,右边大
            int temp = 0;
            if (i<j)
            {
                temp = array[j];
                array[j] = array[i];
                array[i] = temp;
            }

        }

        // 将中位值归位
        array[left] = array[i];
        array[i] = base;

        // 将中值左,右侧的数据分别进行排序(递归)
        quickSort(array, left, i-1);
        quickSort(array, i+1, right);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9,4,1,6,7,2,5};
        quickSort(arr, 0 , arr.length - 1);
        for (int i :
                arr) {
            System.out.println(i);
        }
    }
}
